package Other;


import java.util.*;

public class leet_offer_38 {
// 剑指offer 38题
    public static void main(String[] args) {
        Solution_38 p = new Solution_38();
        String s = "aab";
        List<String> valueList = Arrays.asList(p.permutation(s));
        System.out.println(valueList.toString());

    }
}

/**
 * 这道题本质就是考察的一个排列问题(去重) 利用回溯算法的几大步就可以很轻松的解决该问题
 */
class Solution_38{
    // 建立一个去重的hash列表
    Set valueList = new HashSet();
    public String[] permutation(String s) {
        // 定义是否使用
        boolean[] used = new boolean[s.length()];
        PermutationAndCombination(s, s.length(), "", used);
        String[] strValue = (String[]) valueList.toArray(new String[valueList.size()]);
        return strValue;
    }

    /**
     * 排列组合
     * @param s         总的字符集
     * @param endTime   字符串的长度
     * @param strValue  已经排好序的字符串
     * @param used      元素下标使用情况
     */
    public void PermutationAndCombination(String s, int endTime,String strValue, boolean[] used){
        if(strValue.length() == endTime){
            valueList.add(strValue);
            return;
        }

        for(int i=0; i<s.length(); i++){
            String tmpChar = String.valueOf(s.charAt(i));
            // 如果字符重复
            if(used[i]) {
                continue;
            }else{
                used[i]=true;
                strValue = strValue + tmpChar;
                PermutationAndCombination(s, endTime, strValue, used);
                // 上面进行操作 下面2步都是进行回溯到起始状态
                strValue = strValue.substring(0, strValue.length()-1);
                used[i]=false;
            }
        }
    }


}

